// 单调栈

/** 
 * 每日温度；时间复杂度为O(n)
 * 请根据每日 气温 列表，重新生成一个列表。
 * 对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。
 * 如果气温在这之后都不会升高，请在该位置用 0 来代替。
 * @param temperatures 气温列表
 * @returns
 */
export function dailyTemperatures(temperatures: number[]): number[] {
  const length: number = temperatures.length;
  const stack: number[] = [];
  const resArr: number[] = new Array(length).fill(0);
  stack.push(0);
  for (let i = 1; i < length; i++) {
    let top = stack[stack.length - 1];
    while (stack.length > 0 && temperatures[top] < temperatures[i]) {
      resArr[top] = i - top;
      stack.pop();
      top = stack[stack.length - 1];
    }
    stack.push(i);
  }
  return resArr;
}

/** 
 * 接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * @param height
 * @returns
 */
export function trap(height: number[]): number {
  const length: number = height.length;
  const stack: number[] = [];
  stack.push(0);
  let resVal: number = 0;
  for (let i = 1; i < length; i++) {
    let top = stack[stack.length - 1];
    if (height[top] > height[i]) {
      stack.push(i);
    } else if (height[top] === height[i]) {
      stack.pop();
      stack.push(i);
    } else {
      while (stack.length > 0 && height[top] < height[i]) {
        let mid = stack.pop();
        if (stack.length > 0) {
          let left = stack[stack.length - 1];
          let h = Math.min(height[left], height[i]) - height[mid!];
          let w = i - left - 1;
          resVal += h * w;
          top = stack[stack.length - 1];
        }
      }
      stack.push(i);
    }
  }
  return resVal;
}

/** 
 * 柱状图中最大的矩形
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * @param heights
 * @returns
 */
export function largestRectangleArea(heights: number[]): number {
  heights.push(0);
  const length: number = heights.length;
  // 栈底->栈顶：严格单调递增
  const stack: number[] = [];
  stack.push(0);
  let resMax: number = 0;
  for (let i = 1; i < length; i++) {
    let top = stack[stack.length - 1];
    if (heights[top] < heights[i]) {
      stack.push(i);
    } else if (heights[top] === heights[i]) {
      stack.pop();
      stack.push(i);
    } else {
      while (stack.length > 0 && heights[top] > heights[i]) {
        let mid = stack.pop();
        let left = stack.length > 0 ? stack[stack.length - 1] : -1;
        let w = i - left - 1;
        let h = heights[mid!];
        resMax = Math.max(resMax, w * h);
        top = stack[stack.length - 1];
      }
      stack.push(i);
    }
  }
  return resMax;
}
